// 给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
// 字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。
// （例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
// 字符串s和t，在s的子序列中t出现的个数
// 五部曲

// 1. 确定dp数组的含义，`dp[i][j]`，以i-1结尾的s子序列中出现以j-1结尾的t的个数
// 2. 递推公式
// ```js
// if(s[i-1] === t[j-1]) {
//     // 用s[i-1]，或者不用，两种情况都可能匹配，因为我们求s的子序列，所以这里只考虑s[i-1]匹配或者不匹配
//     dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
// } else {
//     dp[i][j] = dp[i-1][j]
// }
// ```
// 3. dp数组的初始化，`dp[i][j]`是从上方和左上方推导而来，`dp[i][0]和dp[0][j]`需要初始化
// ```js
// dp[i][0] = 1 // 以i-1结尾的字符串，出现空字符串的个数
// dp[0][j] = 0
// dp[0][0] = 1 // 空字符串，出现空字符串的个数为1
// ```
// 4. 遍历顺序，左上方和正上方
// 5. 举例推导dp

// ```js

function numDistinct(s, t) {
    let dp = new Array(s.length + 1).fill(0).map(_ => new Array(t.length + 1).fill(0))
    for (let i = 0; i <= s.length; i++) {
        dp[i][0] = 1        
    }
    for (let i = 1; i <= s.length; i++) {
        for (let j = 1; j <= t.length; j++) {
            if (s[i - 1] === t[j - 1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j]
            }          
        }
    }
    return dp[s.length][t.length]
}

let s = 'rabbbit', t = 'rabbit'
console.log(numDistinct(s, t))